public class MySingleList{

    static class ListNone {
        public int val;
        public ListNone next;


        public ListNone(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }
    }

    public ListNone head;     //表示当前列表的头节点

    public int listSize;



    //链表分割
    public ListNone partition(int x) {
        ListNone bs = null;
        ListNone be = null;
        ListNone as = null;
        ListNone ae = null;

        ListNone cur = head;

        while (cur != null) {
            if(cur.val < x) {
                //第一次插入
                if(bs == null) {
                    bs = be = cur;
                } else {
                    be.next = cur;
                    be = cur;
                }
            } else {
                if(as == null) {
                    as = ae = cur;
                } else {
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }
        be.next = as;
        if(as != null) {
            ae.next = null;
        }
        return bs;
    }


    //链表的回文结构
    public boolean chkPalindrome() {
        if(head == null) {
            return false;
        }
        if(head.next == null) {
            return true;
        }

        ListNone fast = head;
        ListNone slow = head;
        //找到链表的一半
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //2.开始翻转后半部分
        ListNone cur = slow.next;
        while (cur != null) {
            ListNone curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }

        //3.一个从头开始走，一个从尾开始走
        while(head != slow) {
            if(head.val != slow.val) {
                return false;
            }
            if(head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }


//找出两个链表的第一个公共节点是哪个
    public ListNone getIntersectionNode(ListNone headA,ListNone headB) {
        //1.假定A链表长，B链表短
        ListNone pl = headA;
        ListNone ps = headB;

        //2.分别求两链表的长度
        int len1 = 0;
        int len2 = 0;
      while(pl != null) {
          len1++;
          pl = pl.next;
      }
        while(ps != null) {
            len2++;
            ps = ps.next;
        }

        pl = headA;
        ps = headB;
        //3.求差值
        int len = 0;
        //若len<0 ---》pl = headB    ps = headA    len = len2 - len1
        len = len1 - len2;
        if(len < 0) {
            //4.确定 pl 指向的链表一定是长链表，ps指向的链表是短链表
            pl = headB;
            ps = headA;

            len = len2 - len1;
        }
        //5.让pl走len步
            while(len != 0) {
                pl = pl.next;
                len--;
        }
            //6.ps和pl同时走，直到相遇      还要考虑不相遇的情况
      while(pl != null && ps != null){
          if(pl == ps) {
              return  pl;
          }
          pl = pl.next;
          ps = ps.next;
      }

         return null;
    }

    //判断链表中是否有环
    public boolean hasCycle(ListNone head) {
        ListNone fast = head;
        ListNone slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }

    public void createLoop(){
        ListNone cur = head;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next.next = head.next.next.next;
    }

}